public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();

        // 测试排序算法
        // -1 空数组测试
//        int[] nums = new int[]{};
        // -2 有序数组测试
//        int[] nums = new int[]{1,2,3,4,5};
        // -3 倒序数组测试
//        int[] nums = new int[]{5,4,3,2,1};
        // -4 乱序
//        int[] nums = new int[]{4,2,5,1,3};
        // -5 重复数组
        int[] nums = new int[]{7, 7, 7, 1, 7};
        s.insertSort(nums);
        for(int e: nums) {
            System.out.print(e + " ");
        }
    }

    public void insertSort(int[] nums) {
        /**
         * 直接插入排序
         * 排序算法思想：
         *  我们默认，在插入第i（i>=1）个元素时，默认i-1之前的所有元素均有序
         *  排升序时，在此基础上，我们假设插入元素为x，只需找到第一个小于等于x的元素插入即可，此时必定有序
         * 各类情况讨论：
         *   1，插入元素有序位置为第一个时：当前置下标为-1时处理
         *   2，插入元素有序位置为最后一个时：由于前一个元素必定小于等于x，故不会循环执行，此时已处理
         *   3，插入元素为中间时：由于前一个元素必定小于等于x，故不会循环执行，此时已处理
         * 实际实现1：
         *   从下标1开始，枚举每一个元素，将该元素持续向前比较，直至遇见小于等于该元素（正确有序位置） 或 -1（正确有序位置）停止
         * 实际实现2：
         *   1的实现并不具备直接插入排序的时间复杂度，因为其多了很多交换开销，我们正确的核心思想应当为“直接步进找正确位置，后续一次赋值”
         *   具体代码逻辑为：
         *      ① 保存当前枚举元素值
         *      ② 持续向前搜索有序位置（temp>=nums[j]），若不是有序位置，则元素后移
         *      ③ 若是有序位置，则将有序位置处修改为枚举值*/
        // 1 预处理
        int n = nums.length;

        // 2 排序逻辑
        for(int i = 1; i < n; i++) { // -nums[i]表示当前待排序元素
            int tempValue = nums[i];
            int j = i-1;
            while(j > -1 && nums[j] > tempValue) { // -nums[j]表示单次遍历元素，若是当前元素有效且不是正确有序元素，则后移并向前寻找
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = tempValue;
        }
    }

    private void swap(int i, int j, int[] nums) {
        /**
         * 交换两下标元素*/
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
